package com.Algorithm.DynamicProgramming.三角形问题;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2022/04/11/15:23
 * @Description:
 * @Target:
 */
public class 最小花费爬楼梯 {
    /*
    * 描述
        给定一个整数数组 cost   ，其中 cost[i]  是从楼梯第i个台阶向上爬需要支付的费用，下标从0开始。
        一旦你支付此费用，即可选择向上爬一个或者两个台阶。

        你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

        请你计算并返回达到楼梯顶部的最低花费。

        数据范围：数组长度满足   \1≤n≤10^5
           ，数组中的值满足 1≤cost i≤10^4

        示例1
        输入：
        [2,5,20]
        返回值：
        5
        说明：
        你将从下标为1的台阶开始，支付5 ，向上爬两个台阶，到达楼梯顶部。总花费为5
        示例2
        输入：
        [1,100,1,1,1,90,1,1,80,1]

        返回值：
        6

        说明：
        你将从下标为 0 的台阶开始。
        1.支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
        2.支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
        3.支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
        4.支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
        5.支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
        6.支付 1 ，向上爬一个台阶，到达楼梯顶部。
        总花费为 6 。
* */


    static int dp(int[] ints,int index,int[] memory){

        if (index<0||index > ints.length-1){
            return 0;
        }

        if (memory[index]!=0){
            return memory[index];
        }

         return  memory[index] = Math.min(dp(ints,index+1,memory),dp(ints,index+2,memory))+ints[index];
        }



    public static void main(String[] args) {
        int[] ints = new int[]{1,100,1,1,1,90,1,1,80,1,0};
        int[] memory = new int[ints.length];
        System.out.println(Math.min(dp(ints,0,memory),dp(ints,1,memory)));


    }
}
